1. Field of the Invention
This invention relates to a data compression apparatus, method and system for compressing input data.
2. Description of the Related Art
In conventional data compression apparatuses for compressing input data, data is compressed by dealing with data as a set of words having a specific number of bytes, and allocating a code having a short bit length and a code having a long bit length to a word of high frequency of appearance and to a word of low frequency of appearance, respectively, by utilizing deviation in the frequency distribution of words. Huffman coding is well-known as such a compression method.
In such a compression method, however, it is necessary to first form the frequency distribution of data. As a result, data cannot be processed through a single path.
In order to solve such a problem, a universal encoding method called a Bentley-Sleator-Tarjan-Wei (BSTW) algorithm has been developed as a method for processing data through a single path. In this encoding method, a dictionary of words in data is shared by encoding and decoding. When a word provided in the dictionary appears in data, the dictionary is updated according to processing called head movement in which the word is moved to the head (or a leading portion) of the dictionary. Accordingly, as head movement is continued, words having high frequencies of appearance are collected to a leading portion of the dictionary. Since information relating to the position of each word registered in the dictionary is output as an code output, a word having a high frequency of appearance is output as information relating to a position close to the head of the dictionary. If short code lengths and long code lengths are allocated to information relating to positions close to the head and to information relating to positions separated from the head, respectively, short code lengths and long code lengths are allocated to words having high frequencies of appearance and to words having low frequencies of appearance, respectively, so that compression of code lengths in the entire information is realized.
The above-described Huffman codes, areas codes and the like are used as variable-length codes.
In the above-described conventional methods, however, in order to change the position of an existing word in the dictionary, it is necessary to retrieve the word in the dictionary. Since the arrangement of a word within the dictionary depends on the state of appearance of the word and words are not sorted, the retrieval must be performed by comparing the word with each word in the dictionary. Accordingly, when retrieving the word starting from the head of the dictionary, it is necessary to compare the word with almost all words in the dictionary if the word has a low frequency of appearance, resulting in a large amount of time for encoding processing.
Furthermore, when outputting image data including a plurality of objects to be drawn (depicted) in a printing apparatus, it is necessary, in some cases, to repeat compression and expansion of the image data a plurality of times. Hence, if a large amount of time is required for encoding processing, an output time becomes a time required for compression and expansion multipled by the plurality of times.